# -*- coding: UTF-8 -*-
import random

class PlacementAleatoire:
    def placementElement(elementPlancheDeJeu, ligne):
        if len(ligne.listeElements) >= 2:
            plusGrandGap = -1
            frereGauche = None
            for i in range(len(ligne.listeElements)):
                extremiteA = ligne.listeElements[i].pos.x + ligne.listeElements[i].largeur
                extremiteB = -1
                if i+1 != len(ligne.listeElements):
                    extremiteB = ligne.listeElements[i+1].pos.x
                else:
                    extremiteB = ligne.largeur
                gap = extremiteB - extremiteA
                if gap > plusGrandGap:
                    plusGrandGap = gap
                    frereGauche = ligne.listeElements[i]
            
            #Va tenter � cinq reprises de placer l'auto
            OK = False
            i = 0
            while i<5 and not OK:
                elementPlancheDeJeu.pos.x = random.uniform(frereGauche.pos.x+frereGauche.largeur+ligne.gapMinimal, frereGauche.pos.x+frereGauche.largeur+plusGrandGap-ligne.gapMinimal)
                if not PlacementAleatoire.collisionElementsLigne(elementPlancheDeJeu, ligne):
                    ligne.listeElements.append(elementPlancheDeJeu)
                    OK = True
                    
                i+=1
                    
        else:
            OK = False
            while not OK:
                pos = random.uniform(0,ligne.largeur-elementPlancheDeJeu.largeur-ligne.gapMinimal)
                elementPlancheDeJeu.pos.x = pos
                if not PlacementAleatoire.collisionElementsLigne(elementPlancheDeJeu, ligne):
                    OK = True
                    ligne.listeElements.append(elementPlancheDeJeu)
            
        if len(ligne.listeElements) > 1:
            ligne.listeElements = PlacementAleatoire.triRapideElements(ligne.listeElements)
            
        return ligne
    
    placementElement = staticmethod(placementElement)
            
    #Va aussi v�rifier qu'il y a un gap correct entre les �lements
    def collisionElementsLigne(aAjouter, ligne):
        #print "EL GAPPPP ::::::" + str(ligne.gapMinimal)
        if len(ligne.listeElements) == 0:
            return False
        
        for i in ligne.listeElements:
            if aAjouter.pos.x + aAjouter.largeur + ligne.gapMinimal < i.pos.x:
                pass
            elif aAjouter.pos.x > i.pos.x+i.largeur + ligne.gapMinimal:
                pass
            else:
                return True
                
        return False
    
    collisionElementsLigne = staticmethod(collisionElementsLigne)
            
    def triRapideElements(L):
        """Tri une liste gr�ce � la variable pos"""
        def trirap(L, g, d):
            pivot = L[(g+d)//2].pos.x
            i = g
            j = d
            while True:
                while L[i].pos.x<pivot:
                    i+=1
                while L[j].pos.x>pivot:
                    j-=1
                if i>j:
                    break
                if i<j:
                    L[i], L[j] = L[j], L[i]
                i+=1
                j-=1
            if g<j:
                trirap(L,g,j)
            if i<d:
                trirap(L,i,d)
     
        g=0
        d=len(L)-1
        trirap(L,g,d)
        return L
    
    triRapideElements = staticmethod(triRapideElements)